<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/13/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/13/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/11/136/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/11/136/" itemprop="url">PAT B1030/A1085</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-11T17:25:00+00:00">
                2017-02-11
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M &lt;= m * p，则称这个数列是完美数列。</p>
<p>现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。</p>
<p>输入格式：</p>
<p>输入第一行给出两个正整数N和p，其中N（&lt;= 10<sup>5</sup>）是输入的正整数的个数，p（&lt;= 10<sup>9</sup>）是给定的参数。第二行给出N个正整数，每个数不超过10<sup>9</sup>。</p>
<p>输出格式：</p>
<p>在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。</p>
<p>输入样例：<br>10 8<br>2 3 20 4 5 1 6 7 8 9<br>输出样例：<br>8</p>
<p>Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M &lt;= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.</p>
<p>Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (&lt;= 105) is the number of integers in the sequence, and p (&lt;= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.</p>
<p>Sample Input:<br>10 8<br>2 3 20 4 5 1 6 7 8 9<br>Sample Output:<br>8</p>
<p>二分法<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">int n, p, a[maxn];</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;p);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;a[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(a, a + n);</span><br><span class="line">    int ans = 1;</span><br><span class="line">    for (int i = 0; i &lt; n ; i++) &#123;</span><br><span class="line">        //在a[i+1]~a[n-1]中查找第一个超过a[i]*p，返回其位置给j</span><br><span class="line">        int j = upper_bound(a + i + 1, a + n, (long long)a[i] * p) - a;</span><br><span class="line">        ans = max(ans , j - i);</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, ans);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>two pointers法<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">//#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, p, a[maxn];</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;p);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;a[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(a, a + n);</span><br><span class="line">    int i = 0, j = 0, count = 1;</span><br><span class="line">    while (i &lt; n &amp;&amp; j &lt; n) &#123;</span><br><span class="line">        while (j &lt;n &amp;&amp; a[j] &lt;= (long long) a[i] * p) &#123;</span><br><span class="line">            count = max(count, j - i + 1);</span><br><span class="line">            j++;</span><br><span class="line">        &#125;</span><br><span class="line">        i++;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, count);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/11/134/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/11/134/" itemprop="url">PAT A1038</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-11T15:55:00+00:00">
                2017-02-11
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case gives a positive integer N (&lt;=10000) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print the smallest number in one line. Do not output leading zeros.</p>
<p>Sample Input:<br>5 32 321 3214 0229 87<br>Sample Output:<br>22932132143287<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 10010;</span><br><span class="line">string str[maxn];</span><br><span class="line">bool cmp(string a, string b)&#123;</span><br><span class="line">    return a + b &lt; b + a;//如果a+b &lt; b+a 就把a排在前面</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n;</span><br><span class="line">    cin &gt;&gt; n;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        cin &gt;&gt; str[i];</span><br><span class="line">    &#125;</span><br><span class="line">    sort(str, str + n, cmp);</span><br><span class="line">    string ans;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        ans += str[i];</span><br><span class="line">    &#125;</span><br><span class="line">    while (ans.size() != 0 &amp;&amp; ans[0] == &apos;0&apos;) &#123;</span><br><span class="line">        ans.erase(ans.begin());//去除前导0</span><br><span class="line">    &#125;</span><br><span class="line">    if (ans.size() == 0) &#123;</span><br><span class="line">        cout &lt;&lt; 0;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        cout &lt;&lt; ans;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>对于字符串S1 S2，如果S1+S2 &lt;S2+S1(+表示拼接)，那么把S1放在S2前面。<br>其次string处理字符串真的强！<br>如果串的大小不为0，要去除前面的所有0；<br>附上需要用上的string函数（需要引用iostream 和 string）<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">(1) += 直接拼接</span><br><span class="line">(2) == != &lt; &lt;= &gt; &gt;= 比较大小 字典序</span><br><span class="line">(3) length()/size() 返回string的长度</span><br><span class="line">(4) insert()</span><br><span class="line">    1. str.insert(pos,string) 在pos位置插入字符串string</span><br><span class="line">    2. str.insert(it,it2,it3) 在it的位置插入字符串的首尾it2,it3</span><br><span class="line">(5) erase()</span><br><span class="line">    1. str.erase(it) 删除单个元素，it为元素迭代器</span><br><span class="line">    2. str.erase(first, last) 删除区间内的所有元素 first和last都为元素迭代器</span><br><span class="line">    3. str.erase(pos,length) pos为需要开始删除的起始位置</span><br><span class="line">(6) clear() 清空string中的数据</span><br><span class="line">(7) substr(pos,len) 返回从pos号开始的长度为len的子串</span><br><span class="line">(8) string:npos 常数，本身值为-1 用以作为find函数失败匹配时的返回值。在unsigned_int类型中 -1 也为4294967295</span><br><span class="line">(9) find()</span><br><span class="line">    1. str.find(str2) 返回str2在str中的位置，如果没找到，则返回string:npos</span><br><span class="line">    2. str.find(pos, str2) 返回从pos找起的str2在str中的位置，如果没找到，则返回string:npos</span><br><span class="line">(10) replace()</span><br><span class="line">    1. str.replace(pos, len, str2) 把str2 从pos开始，长度为len换成str2</span><br><span class="line">    2. str.replace(it1, it2, str2) 把str的迭代器[it1,it2)范围的子串替换为str2</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/11/133/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/11/133/" itemprop="url">PAT A1067</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-11T15:23:33+00:00">
                2017-02-11
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given any permutation of the numbers {0, 1, 2,…, N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:</p>
<p>Swap(0, 1) =&gt; {4, 1, 2, 0, 3}<br>Swap(0, 3) =&gt; {4, 1, 2, 3, 0}<br>Swap(0, 4) =&gt; {0, 1, 2, 3, 4}</p>
<p>Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case, which gives a positive N (&lt;=105) followed by a permutation sequence of {0, 1, …, N-1}. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each case, simply print in a line the minimum number of swaps need to sort the given permutation.</p>
<p>Sample Input:<br>10 3 5 7 2 6 4 9 0 8 1<br>Sample Output:<br>9</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">int pos[maxn];</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, ans = 0;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    int left = n - 1, num;//left存放除0以外不在本位的数</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;num);</span><br><span class="line">        pos[num] = i;</span><br><span class="line">        if (num == i &amp;&amp; num !=0) &#123;</span><br><span class="line">            left--;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int k = 1;//k存放除了0意外当前不在本位上的最小的数</span><br><span class="line">    while (left &gt; 0) &#123;</span><br><span class="line">        //如果0在本位上，则寻找一个当前不在本位上的数与0交换</span><br><span class="line">        if (pos[0] == 0) &#123;</span><br><span class="line">            while (k &lt; n) &#123;</span><br><span class="line">                if (pos[k] != k) &#123;</span><br><span class="line">                    swap(pos[0], pos[k]);</span><br><span class="line">                    ans++;</span><br><span class="line">                    break;</span><br><span class="line">                &#125;</span><br><span class="line">                k++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        //只要0不在本位，就将0所在的位置的数的当前所处位置与0的位置交换</span><br><span class="line">        while (pos[0] != 0) &#123;</span><br><span class="line">            swap(pos[0], pos[pos[0]]);</span><br><span class="line">            ans++;</span><br><span class="line">            left--;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, ans);</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/11/132/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/11/132/" itemprop="url">PAT A1037</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-11T14:53:05+00:00">
                2017-02-11
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!</p>
<p>For example, given a set of coupons {1 2 4 -1}, and a set of product values {7 6 -2 -3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.</p>
<p>Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here 1&lt;= NC, NP &lt;= 105, and it is guaranteed that all the numbers will not exceed 230.</p>
<p>Output Specification:</p>
<p>For each test case, simply print in a line the maximum amount of money you can get back.</p>
<p>Sample Input:<br>4<br>1 2 4 -1<br>4<br>7 6 -2 -3<br>Sample Output:<br>43<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">int coupon[maxn], products[maxn];</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, m;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;coupon[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;m);</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;products[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(coupon, coupon + n);</span><br><span class="line">    sort(products, products + m);</span><br><span class="line">    int i = 0, j, ans = 0;</span><br><span class="line">    while (i &lt; n &amp;&amp; i &lt; m &amp;&amp; coupon[i] &lt; 0 &amp;&amp; products[i] &lt; 0) &#123;</span><br><span class="line">        ans += coupon[i] * products[i];</span><br><span class="line">        i++;</span><br><span class="line">    &#125;</span><br><span class="line">    i = n - 1;</span><br><span class="line">    j = m - 1;</span><br><span class="line">    while (i &gt;= 0 &amp;&amp; j &gt;= 0 &amp;&amp; coupon[i] &gt; 0 &amp;&amp; products[j] &gt;0) &#123;</span><br><span class="line">        ans += coupon[i] * products[j];</span><br><span class="line">        i--;j--;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;,ans);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/11/131/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/11/131/" itemprop="url">PAT A1033</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-11T13:49:00+00:00">
                2017-02-11
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (&lt;= 100), the maximum capacity of the tank; D (&lt;=30000), the distance between Hangzhou and the destination city; Davg (&lt;=20), the average distance per unit gas that the car can run; and N (&lt;= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (&lt;=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.</p>
<p>Sample Input 1:<br>50 1300 12 8<br>6.00 1250<br>7.00 600<br>7.00 150<br>7.10 0<br>7.20 200<br>7.50 400<br>7.30 1000<br>6.85 300<br>Sample Output 1:<br>749.17<br>Sample Input 2:<br>50 1300 12 2<br>7.10 0<br>7.00 600<br>Sample Output 2:<br>The maximum travel distance = 1200.00<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn = 510;</span><br><span class="line">const int INF = 1.0e9;</span><br><span class="line">struct station&#123;</span><br><span class="line">    double price, dis;//单价和离杭州的距离</span><br><span class="line">&#125;st[maxn];</span><br><span class="line">bool cmp (station a, station b)&#123;</span><br><span class="line">    return a.dis &lt; b.dis;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n;</span><br><span class="line">    double Cmax, D, Davg;</span><br><span class="line">    scanf(&quot;%lf%lf%lf%d&quot;, &amp;Cmax, &amp;D, &amp;Davg, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%lf%lf&quot;, &amp;st[i].price, &amp;st[i].dis);//各加油站距离</span><br><span class="line">    &#125;</span><br><span class="line">    st[n].price = 0;</span><br><span class="line">    st[n].dis = D;</span><br><span class="line">    sort(st, st + n , cmp);</span><br><span class="line">    if (st[0].dis != 0) &#123;</span><br><span class="line">        printf(&quot;The maximum travel distance = 0.00\n&quot;);//出发点没有加油站，无法出发</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        int now = 0;//当前所处的加油站编号</span><br><span class="line">        //总花费，当前油量 满油行驶距离</span><br><span class="line">        double ans = 0, nowTank = 0, MAX = Cmax * Davg;</span><br><span class="line">        while (now &lt; n) &#123;</span><br><span class="line">            //每次循环将选出下一个需要到达的加油站</span><br><span class="line">            //选出从当前加油站满油能到达范围的第一个油价低于当前油价的加油站</span><br><span class="line">            //如果没有低于当前油价的加油站，则选择价格最低的那个</span><br><span class="line">            int k = -1;//油价最低的加油站编号</span><br><span class="line">            double priceMin = INF;//最低油价</span><br><span class="line">            for (int i = now + 1; i &lt;= n &amp;&amp; st[i].dis - st[now].dis &lt;= MAX; i++) &#123;</span><br><span class="line">                if (st[i].price &lt; priceMin) &#123;</span><br><span class="line">                    priceMin = st[i].price;</span><br><span class="line">                    k = i;</span><br><span class="line">                    //找到了第一个油价低于当前油价的加油站，中断循环</span><br><span class="line">                    if (priceMin &lt; st[now].price) &#123;</span><br><span class="line">                        break;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            if (k == -1) &#123;</span><br><span class="line">                break;//满油无法到达下一个加油站，退出循环</span><br><span class="line">            &#125;</span><br><span class="line">            //下面为能找到可到达的加油站k，计算转移花费</span><br><span class="line">            //need为从now到k所需要的油量</span><br><span class="line">            double need = (st[k].dis - st[now].dis) / Davg;</span><br><span class="line">            if (priceMin &lt; st[now].price) &#123;//如果加油站k的油价低于当前油价</span><br><span class="line">                //只买足够到达加油站k的油</span><br><span class="line">                if (nowTank &lt; need) &#123;//当前油量不足need</span><br><span class="line">                    ans += (need - nowTank) * st[now].price;//补足need</span><br><span class="line">                    nowTank = 0;//到达加油站k后油量变为0</span><br><span class="line">                &#125;else&#123;</span><br><span class="line">                    nowTank -= need;//油量足够，直接到达加油站k</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;else&#123;//如果加油站k的油价高于当前油价</span><br><span class="line">                ans += (Cmax - nowTank) * st[now].price;//加满油</span><br><span class="line">                nowTank = Cmax - need;//加满油后到达加油站k剩余</span><br><span class="line">            &#125;</span><br><span class="line">            now = k;//到达加油站k</span><br><span class="line">        &#125;</span><br><span class="line">        if (now == n)&#123;</span><br><span class="line">            //到达目的地</span><br><span class="line">            printf(&quot;%.2f\n&quot;, ans);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            printf(&quot;The maximum travel distance = %.2f\n&quot;, st[now].dis + MAX);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>策略1：优先前往油价更低的加油站<br>策略2：在没有更低油价的加油站时，往油价尽可能低的加油站<br>合并在一起，就是在所有满油状态能到达的加油站中，选出油价最低的那个加油站，而一旦在枚举过程中找到了第一个油价低于当前油价的加油站，则退出循环，结束选择过程。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/11/130/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/11/130/" itemprop="url">PAT B1020/A1070</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-11T13:24:36+00:00">
                2017-02-11
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。</p>
<p>注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼，获得 72 + 45/2 = 94.5（亿元）。</p>
<p>输入格式：</p>
<p>每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最大需求量。随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。</p>
<p>输出格式：</p>
<p>对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后2位。</p>
<p>输入样例：<br>3 20<br>18 15 10<br>75 72 45<br>输出样例：<br>94.50</p>
<p>Mooncake is a Chinese bakery product traditionally eaten during the Mid-Autumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the region’s culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to tell the maximum profit that can be made.</p>
<p>Note: partial inventory storage can be taken. The sample shows the following situation: given three kinds of mooncakes with inventory amounts being 180, 150, and 100 thousand tons, and the prices being 7.5, 7.2, and 4.5 billion yuans. If the market demand can be at most 200 thousand tons, the best we can do is to sell 150 thousand tons of the second kind of mooncake, and 50 thousand tons of the third kind. Hence the total profit is 7.2 + 4.5/2 = 9.45 (billion yuans).</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 positive integers N (&lt;=1000), the number of different kinds of mooncakes, and D (&lt;=500 thousand tons), the maximum total demand of the market. Then the second line gives the positive inventory amounts (in thousand tons), and the third line gives the positive prices (in billion yuans) of N kinds of mooncakes. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print the maximum profit (in billion yuans) in one line, accurate up to 2 decimal places.</p>
<p>Sample Input:<br>3 200<br>180 150 100<br>7.5 7.2 4.5<br>Sample Output:<br>9.45<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">struct mooncake&#123;</span><br><span class="line">    double store;//存量</span><br><span class="line">    double sell;//总销售价</span><br><span class="line">    double price;//单价</span><br><span class="line">&#125;moon[1010];</span><br><span class="line">bool cmp(mooncake a, mooncake b)&#123;</span><br><span class="line">    return a.price &gt; b.price;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, d;</span><br><span class="line">    double sum = 0.0;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;d);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%lf&quot;, &amp;moon[i].store);</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%lf&quot;, &amp;moon[i].sell);</span><br><span class="line">        moon[i].price = moon[i].sell / moon[i].store;</span><br><span class="line">    &#125;</span><br><span class="line">    sort(moon, moon + n, cmp);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        if (moon[i].store &lt;= d) &#123;//存量不能满足要求</span><br><span class="line">            sum += moon[i].sell;</span><br><span class="line">            d -= moon[i].store;</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            sum += moon[i].price * d ;</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%.2f\n&quot;, sum);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/11/128/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/11/128/" itemprop="url">PAT B1023</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-11T13:16:00+00:00">
                2017-02-11
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>给定数字0-9各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意0不能做首位）。例如：给定两个0，两个1，三个5，一个8，我们得到的最小的数就是10015558。</p>
<p>现给定数字，请编写程序输出能够组成的最小的数。</p>
<p>输入格式：</p>
<p>每个输入包含1个测试用例。每个测试用例在一行中给出10个非负整数，顺序表示我们拥有数字0、数字1、……数字9的个数。整数间用一个空格分隔。10个数字的总个数不超过50，且至少拥有1个非0的数字。</p>
<p>输出格式：</p>
<p>在一行中输出能够组成的最小的数。</p>
<p>输入样例：<br>2 2 0 0 0 3 0 0 1 0<br>输出样例：<br>10015558</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">int num[10];//0-9的个数</span><br><span class="line">int main()&#123;</span><br><span class="line">    int cnt = 0;//位数</span><br><span class="line">    for (int i = 0; i &lt; 10; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;num[i]);//读入数字</span><br><span class="line">        cnt++;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt; 10; i++) &#123;//第一位要在1-9之间找一个最小的输出</span><br><span class="line">        if (num[i]) &#123;</span><br><span class="line">            printf(&quot;%d&quot;, i);</span><br><span class="line">            num[i]--;</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; 10; i++) &#123;</span><br><span class="line">        for (int j = 0; j &lt; num[i]; j++) &#123;</span><br><span class="line">            printf(&quot;%d&quot;, i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/127/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/127/" itemprop="url">PAT A1048</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T17:14:00+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as 105 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (&lt;=105, the total number of coins) and M(&lt;=103, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the two face values V1 and V2 (separated by a space) such that V1 + V2 = M and V1 &lt;= V2. If such a solution is not unique, output the one with the smallest V1. If there is no solution, output “No Solution” instead.</p>
<p>Sample Input 1:<br>8 15<br>1 2 8 7 2 4 11 15<br>Sample Output 1:<br>4 11<br>Sample Input 2:<br>7 14<br>1 8 7 2 4 11 15<br>Sample Output 2:<br>No Solution</p>
<p>散列法：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">int hashTable[1005];</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, m, a;</span><br><span class="line">    scanf(&quot;%d %d&quot;, &amp;n, &amp;m);</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;a);</span><br><span class="line">        ++hashTable[a];</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; 1005; i++) &#123;</span><br><span class="line">        if (hashTable[i] != 0 &amp;&amp; hashTable[m - i] != 0) &#123;</span><br><span class="line">            if (i == (m - i) &amp;&amp; hashTable[i] &lt;= 1) &#123;</span><br><span class="line">                continue;</span><br><span class="line">            &#125;</span><br><span class="line">            printf(&quot;%d %d\n&quot;, i , m - i);</span><br><span class="line">            return 0;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;No Solution\n&quot;);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>二分法：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">//#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">int a[100010];</span><br><span class="line">//left和right初始分别为0和n-1，key即m-a[i]</span><br><span class="line">int Bin(int left,int right, int key)&#123;</span><br><span class="line">    int mid;</span><br><span class="line">    while (left&lt;=right) &#123;</span><br><span class="line">        mid = (left+right)/2;</span><br><span class="line">        if(a[mid]==key)return mid;</span><br><span class="line">        else if(a[mid] &gt; key) right = mid - 1;</span><br><span class="line">        else left = mid + 1;</span><br><span class="line">    &#125;</span><br><span class="line">    return -1;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int i, n, m;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);</span><br><span class="line">    for (i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;a[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(a, a+n);</span><br><span class="line">    for (i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        int pos = Bin(0, n-1, m-a[i]);</span><br><span class="line">        if (pos != -1 &amp;&amp; pos != i) &#123;</span><br><span class="line">            printf(&quot;%d %d\n&quot;, a[i], a[pos]);</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    if (i == n) &#123;</span><br><span class="line">        printf(&quot;No Solution\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/125/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/125/" itemprop="url">PAT A1050</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T16:53:09+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given two strings S1 and S2, S = S1 - S2 is defined to be the remaining string after taking all the characters in S2 from S1. Your task is simply to calculate S1 - S2 for any given strings. However, it might not be that simple to do it fast.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case consists of two lines which gives S1 and S2, respectively. The string lengths of both strings are no more than 104. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.</p>
<p>Output Specification:</p>
<p>For each test case, print S1 - S2 in one line.</p>
<p>Sample Input:<br>They are students.<br>aeiou<br>Sample Output:<br>Thy r stdnts.<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;algorithm&quot;</span><br><span class="line">//using namespace std;</span><br><span class="line">char str1[10010], str2[10010];</span><br><span class="line">bool hashTable[256] = &#123;false&#125;;</span><br><span class="line">int main()&#123;</span><br><span class="line">    gets(str1);</span><br><span class="line">    gets(str2);</span><br><span class="line">    int len1 = (int)strlen(str1);</span><br><span class="line">    int len2 = (int)strlen(str2);</span><br><span class="line">    for (int i = 0; i &lt; len2; i++) &#123;</span><br><span class="line">        hashTable[str2[i]] = true;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; len1; i++) &#123;</span><br><span class="line">        if (hashTable[str1[i]] == false) &#123;</span><br><span class="line">            printf(&quot;%c&quot;, str1[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/10/124/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/10/124/" itemprop="url">PAT A1041</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-10T15:43:08+00:00">
                2017-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1, 104]. The first one who bets on a unique number wins. For example, if there are 7 people betting on 5 31 5 88 67 88 17, then the second one who bets on 31 wins.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case contains a line which begins with a positive integer N (&lt;=105) and then followed by N bets. The numbers are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print the winning number in a line. If there is no winner, print “None” instead.</p>
<p>Sample Input 1:<br>7 5 31 5 88 67 88 17<br>Sample Output 1:<br>31<br>Sample Input 2:<br>5 888 666 666 888 888<br>Sample Output 2:<br>None<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;algorithm&quot;</span><br><span class="line">//using namespace std;</span><br><span class="line">int peo[100010];</span><br><span class="line">int hashTable[10010] = &#123;0&#125;;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0 ; i &lt; n ; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;peo[i]);</span><br><span class="line">        hashTable[peo[i]]++;</span><br><span class="line">    &#125;</span><br><span class="line">    bool exist = false;</span><br><span class="line">    for (int i = 0 ; i &lt; n ; i++) &#123;</span><br><span class="line">        if (hashTable[peo[i]] == 1) &#123;</span><br><span class="line">            printf(&quot;%d\n&quot;, peo[i]);</span><br><span class="line">            exist = true;</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    if (exist == false) &#123;</span><br><span class="line">        printf(&quot;None\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/12/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/12/">12</a><span class="page-number current">13</span><a class="page-number" href="/page/14/">14</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/14/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
